{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Palindromic Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPalindromeSubseq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长回文子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，找出其中最长的回文子序列，并返回该序列的长度。</p>\n",
    "\n",
    "<p>子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"bbbab\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>一个可能的最长回文子序列为 \"bbbb\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"cbbd\"\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>一个可能的最长回文子序列为 \"bb\" 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <= 1000</code></li>\n",
    "\t<li><code>s</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-palindromic-subsequence](https://leetcode.cn/problems/longest-palindromic-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-palindromic-subsequence](https://leetcode.cn/problems/longest-palindromic-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"bbbab\"', '\"cbbd\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0, ''] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            prev = [0, '']\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if s[i] == s[j] and s[i] != prev[1]:\n",
    "                    prev, dp[j] = dp[j], [prev[0] + 2, s[i]]\n",
    "                else:\n",
    "                    prev = dp[j]\n",
    "                    if dp[j + 1][0] > dp[j][0]:\n",
    "                        dp[j] = dp[j + 1]\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        ind = defaultdict(list)\n",
    "        for i, va in enumerate(s):\n",
    "            ind[va].append(i)\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = 2\n",
    "            for r in range(x + 1, y):\n",
    "                if s[r] != s[x]:\n",
    "                    val = s[r]\n",
    "                    right = -1\n",
    "                    for rj in ind[val][::-1]:\n",
    "                        if rj < y:\n",
    "                            right = rj\n",
    "                            break\n",
    "\n",
    "                    left = -1\n",
    "                    for li in ind[val]:\n",
    "                        if li > x:\n",
    "                            left = li\n",
    "                            break\n",
    "\n",
    "                    if left < right and left != -1 and right != -1:\n",
    "                        res = max(res, 2 + dfs(left, right))\n",
    "\n",
    "            return res\n",
    "            \n",
    "\n",
    "        # 枚举回文序列的头尾字符\n",
    "        ans = 0\n",
    "        for i, va in enumerate(s):\n",
    "            if ind[va] and ind[va][-1] > i:\n",
    "                length = dfs(i, ind[va][-1])\n",
    "                ans = max(ans, length)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 动态规划\n",
    "# 使用三维动态规划dp[i][j][k]表示s[i:j+1]中以ASCII码为k开头结尾的回文子序列长度\n",
    "# 使用前后缀的最大值维护以非k结尾的子序列长度，使得子序列符合题意\n",
    "class Solution1:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        lst = [ord(w) - ord('a') for w in s]\n",
    "        dp = [[[0] * 26 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for k in range(26):\n",
    "                dp[i][i + 1][k] = int(lst[i] == lst[i + 1] == k) * 2\n",
    "\n",
    "            for j in range(i + 2, n):\n",
    "                if lst[i] != lst[j]:\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k])\n",
    "                else:\n",
    "                    cur = dp[i + 1][j - 1]\n",
    "                    pre = [0] * (26 + 1)\n",
    "                    post = [0] * (26 + 1)\n",
    "                    for x in range(26):\n",
    "                        pre[x + 1] = max(pre[x], cur[x])\n",
    "                        post[26 - x - 1] = max(post[26 - x], cur[26 - x - 1])\n",
    "\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(pre[k], post[k + 1]) + 2 * (lst[i] == k)\n",
    "\n",
    "        return max([max([max(x) for x in d]) for d in dp])\n",
    "\n",
    "\n",
    "\n",
    "# 记忆化搜索\n",
    "# 枚举首尾的字母进行递归记忆化搜索\n",
    "# 向内搜索的时候确保下一个字符与当前不同\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        ind = defaultdict(list)\n",
    "        for i, va in enumerate(s):\n",
    "            ind[va].append(i)\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = 2\n",
    "            for r in range(x + 1, y):\n",
    "                if s[r] != s[x]:\n",
    "                    val = s[r]\n",
    "                    right = -1\n",
    "                    for rj in ind[val][::-1]:\n",
    "                        if rj < y:\n",
    "                            right = rj\n",
    "                            break\n",
    "\n",
    "                    left = -1\n",
    "                    for li in ind[val]:\n",
    "                        if li > x:\n",
    "                            left = li\n",
    "                            break\n",
    "\n",
    "                    if left < right and left != -1 and right != -1:\n",
    "                        res = max(res, 2 + dfs(left, right))\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        # 枚举回文序列的头尾字符\n",
    "        ans = 0\n",
    "        for i, va in enumerate(s):\n",
    "            if ind[va] and ind[va][-1] > i:\n",
    "                length = dfs(i, ind[va][-1])\n",
    "                ans = max(ans, length)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 最长的“好的回文子序列”的长度\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # f[i][j] 表示 i-j 回文子序列最外围的字符\n",
    "        f = [['' for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1): # 区间dp\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                if s[i] == s[j] and s[i] != f[i+1][j-1]: # 满足条件：当前字母相同；且当前字母不等于内层回文序列的最外围字符\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    f[i][j] = s[i] # 新的回文串，最外围字母更新为当前字母\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "                    f[i][j] = f[i+1][j] if dp[i+1][j] > dp[i][j-1] else f[i][j-1]\n",
    "        \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        # dp[i][j] 表示 i~j 最长的“好的回文子序列”的长度\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        # f[i][j] 表示 i-j 回文子序列最外围的字符\n",
    "        f = [['' for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "        for span in range(2, n+1): # 区间dp\n",
    "            for i in range(n-span+1):\n",
    "                j = i + span - 1\n",
    "\n",
    "                if s[i] == s[j] and s[i] != f[i+1][j-1]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                    f[i][j] = s[i]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "                    f[i][j] = f[i+1][j] if dp[i+1][j] > dp[i][j-1] else f[i][j-1]\n",
    "        \n",
    "        return dp[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [[[0,''] for _ in range(n)] for _ in range(n)]\n",
    "        ans = \"\"\n",
    "        for j in range(1,n):\n",
    "            for i in range(j-1,-1,-1):\n",
    "                if s[i] == s[j] and s[j] != f[i+1][j-1][1]:\n",
    "                    f[i][j][0] = f[i+1][j-1][0] + 2\n",
    "                    f[i][j][1] = s[j]\n",
    "                else:\n",
    "                    f[i][j] = f[i][j-1] if f[i][j-1][0] > f[i+1][j][0] else f[i+1][j]\n",
    "\n",
    "        return f[0][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[[0] * 26 for _ in range(n)] for _ in range(n)]\n",
    "        res = 0\n",
    "        for length in range(2, n+1):\n",
    "            for start in range(0, n - length + 1):\n",
    "                end = start + length - 1\n",
    "                for i in range(26):\n",
    "                    dp[start][end][i] = max(dp[start][end - 1][i], dp[start + 1][end][i])\n",
    "                if s[start] == s[end]:\n",
    "                    j = ord(s[start]) - 97\n",
    "                    for i in range(26):\n",
    "                        if i != j:\n",
    "                            dp[start][end][j] = max(dp[start][end][j], dp[start + 1][end - 1][i] + 2)\n",
    "                            res = max(res, dp[start][end][j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # 动态规划\n",
    "# 使用三维动态规划dp[i][j][k]表示s[i:j+1]中以ASCII码为k开头结尾的回文子序列长度\n",
    "# 使用前后缀的最大值维护以非k结尾的子序列长度，使得子序列符合题意\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        lst = [ord(w) - ord('a') for w in s]\n",
    "        dp = [[[0] * 26 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for k in range(26):\n",
    "                dp[i][i + 1][k] = int(lst[i] == lst[i + 1] == k) * 2\n",
    "\n",
    "            for j in range(i + 2, n):\n",
    "                if lst[i] != lst[j]:\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(dp[i + 1][j][k], dp[i][j - 1][k])\n",
    "                else:\n",
    "                    cur = dp[i + 1][j - 1]\n",
    "                    pre = [0] * (26 + 1)\n",
    "                    post = [0] * (26 + 1)\n",
    "                    for x in range(26):\n",
    "                        pre[x + 1] = max(pre[x], cur[x])\n",
    "                        post[26 - x - 1] = max(post[26 - x], cur[26 - x - 1])\n",
    "\n",
    "                    for k in range(26):\n",
    "                        dp[i][j][k] = max(pre[k], post[k + 1]) + 2 * (lst[i] == k)\n",
    "\n",
    "        return max([max([max(x) for x in d]) for d in dp])\n",
    "\n",
    "\n",
    "\n",
    "# 记忆化搜索\n",
    "# 枚举首尾的字母进行递归记忆化搜索\n",
    "# 向内搜索的时候确保下一个字符与当前不同\n",
    "from functools import lru_cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution2:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        ind = defaultdict(list)\n",
    "        for i, va in enumerate(s):\n",
    "            ind[va].append(i)\n",
    "\n",
    "        # 记忆化搜索\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = 2\n",
    "            for r in range(x + 1, y):\n",
    "                if s[r] != s[x]:\n",
    "                    val = s[r]\n",
    "                    right = -1\n",
    "                    for rj in ind[val][::-1]:\n",
    "                        if rj < y:\n",
    "                            right = rj\n",
    "                            break\n",
    "\n",
    "                    left = -1\n",
    "                    for li in ind[val]:\n",
    "                        if li > x:\n",
    "                            left = li\n",
    "                            break\n",
    "\n",
    "                    if left < right and left != -1 and right != -1:\n",
    "                        res = max(res, 2 + dfs(left, right))\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        # 枚举回文序列的头尾字符\n",
    "        ans = 0\n",
    "        for i, va in enumerate(s):\n",
    "            if ind[va] and ind[va][-1] > i:\n",
    "                length = dfs(i, ind[va][-1])\n",
    "                ans = max(ans, length)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        occ = set(s)\n",
    "        que = defaultdict(list)\n",
    "        for i, ch in enumerate(s):\n",
    "            que[ch].append(i)\n",
    "        \n",
    "        @cache\n",
    "        def f(i, j, pre):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == pre:\n",
    "                return f(i + 1, j, pre)\n",
    "            if s[j] == pre:\n",
    "                return f(i, j - 1, pre)\n",
    "            res = 0\n",
    "            for k in reversed(que[s[i]]):\n",
    "                if k <= j and k > i:\n",
    "                    res = 2 + f(i + 1, k - 1, s[i])\n",
    "                    break \n",
    "            for k in que[s[j]]:\n",
    "                if k >= i and k < j:\n",
    "                    res = max(res, 2 + f(k + 1, j - 1, s[j]))\n",
    "            res = max(res, f(i + 1, j - 1, pre))\n",
    "            return res \n",
    "        \n",
    "        return f(0, n - 1, '+')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j, last):\n",
    "            if i >= j: return 0\n",
    "            if s[i] == s[j] and s[i] != last:\n",
    "                return dfs(i + 1, j - 1, s[i]) + 2\n",
    "            return max(dfs(i + 1, j, last), dfs(i, j - 1, last))\n",
    "        res = dfs(0, len(s) - 1, None)\n",
    "        del dfs\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        # 简单，区间DP可以解决问题\n",
    "        # 怎样解决连续字符不相等的问题？\n",
    "        @cache\n",
    "        def f(i, j, last):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j] and s[i] != last:\n",
    "                return 2 + f(i+1, j-1, last=s[i])\n",
    "            return max(f(i+1, j, last), f(i, j-1, last))\n",
    "        ans = f(0, len(s)-1, '*')\n",
    "        f.cache_clear()\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        @cache\n",
    "        def f(L, R, p):\n",
    "            if L == R: return 0\n",
    "            rnt = max(f(L+1, R, p), f(L, R-1, p))\n",
    "            l, r = s.find(s[R-1], L, R), s.rfind(s[L], L, R)\n",
    "\n",
    "            if l != R-1 and s[R-1] != p:\n",
    "                rnt = max(rnt, 2 + f(l+1, R-1, s[R-1]))\n",
    "            if r != L and s[L] != p:\n",
    "                rnt = max(rnt, 2 + f(L+1, r, s[L]))\n",
    "            return rnt\n",
    "        \n",
    "        ans = f(0, len(s), \"-\")\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        NO_PREV = \"#\"\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, last: str) -> int:\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if s[i] == s[j] and s[i] != last:\n",
    "                return 2 + dfs(i + 1, j - 1, s[i])\n",
    "            return max(dfs(i + 1, j, last), dfs(i, j - 1, last))\n",
    "        \n",
    "        return dfs(0, len(s) - 1, NO_PREV)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        # if s == s[::-1]: return len(s)\n",
    "        # result = 0\n",
    "        # for each_s in set(s):\n",
    "        #     if s.count(each_s) % 2 == 0:\n",
    "        #         result += s.count(each_s)\n",
    "        # return result\n",
    "        \n",
    "        # empty input\n",
    "#         if not s: return 0\n",
    "#         if s == s[::-1]: return len(s)\n",
    "        \n",
    "#         # general case: not required to be contiguous\n",
    "#         # largest common subsequence with its reverse\n",
    "#         N = len(s)\n",
    "#         dp = [[0 for _ in range(N+1)] for _ in range(N+1)]\n",
    "#         s1, s2 = s, s[::-1]\n",
    "#         for i in range(N):\n",
    "#             for j in range(N):\n",
    "#                 if s1[i] == s2[j]:\n",
    "#                     if i ==0 or j == 0:\n",
    "#                         dp[i+1][j+1] = 1\n",
    "#                     else:\n",
    "#                         dp[i+1][j+1] = dp[i][j] + 1\n",
    "#                 else:\n",
    "#                     dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])\n",
    "#         return dp[-1][-1]\n",
    "        \n",
    "        \n",
    "        if not s:\n",
    "            return 0\n",
    "        \n",
    "        s_len = len(s)\n",
    "        if s == s[::-1]:\n",
    "            return s_len\n",
    "             \n",
    "        DP_pre_pre = None # for pre pre DP with delta - 2\n",
    "        DP_pre = [1]*s_len # for pre DP with delta - 1\n",
    "        for delta in range(1, s_len):\n",
    "            DP = [1]*s_len\n",
    "            for i in range(s_len - delta):\n",
    "                j = i + delta\n",
    "                if s[i] == s[j]:\n",
    "                    if delta == 1:\n",
    "                        DP[i] = 2\n",
    "                    else:\n",
    "                        DP[i] = DP_pre_pre[i+1] + 2\n",
    "                else:\n",
    "                    DP[i] = max(DP_pre[i], DP_pre[i+1])\n",
    "            DP_pre_pre, DP_pre = DP_pre, DP\n",
    "                    \n",
    "        return DP_pre[0]\t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def longestPalindromeSubseq(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        dp = [1] * n\n",
    "        for j in range(1, len(s)):\n",
    "            pre = dp[j]\n",
    "            for i in reversed(range(0, j)):\n",
    "                tmp = dp[i]\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i] = 2 + pre if i + 1 <= j - 1 else 2\n",
    "                else:\n",
    "                    dp[i] = max(dp[i + 1], dp[i])\n",
    "                pre = tmp\n",
    "        return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        dp = [0] * l\n",
    "        for i in range(l-1, -1, -1):\n",
    "            cur = [0] * l\n",
    "            cur[i] = 1\n",
    "            for j in range(i+1, l):\n",
    "                if s[i] == s[j]:\n",
    "                    cur[j] = dp[j-1] + 2\n",
    "                else:\n",
    "                    cur[j] = max(dp[j], cur[j-1])\n",
    "            dp = cur\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i] = 1\n",
    "            pre = 0  # f[i+1][i]\n",
    "            for j in range(i + 1, n):\n",
    "                tmp = f[j]\n",
    "                f[j] = pre + 2 if s[i] == s[j] else max(f[j], f[j - 1])\n",
    "                pre = tmp\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [0]*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i] = 1\n",
    "            prev = 0\n",
    "            for j in range(i,n-1):\n",
    "                temp = dp[j+1]\n",
    "                if s[i]==s[j+1]:\n",
    "                    dp[j+1] = prev+2\n",
    "                else:\n",
    "                    dp[j+1] = max(dp[j+1], dp[j])\n",
    "                prev= temp\n",
    "        return dp[n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            d[c].append(i)\n",
    "        d = [i for i in d.values() if len(i) > 1]\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            m = j - i\n",
    "            if m <= 1:\n",
    "                return 0 if m < 1 else 1\n",
    "            j -= 1\n",
    "            m = -1\n",
    "            for a in d:\n",
    "                if i > a[-1] or j < a[0]:\n",
    "                    continue\n",
    "                i1 = bisect_left(a, i)\n",
    "                j1 = bisect_right(a, j) - 1\n",
    "                if i1 >= j1:\n",
    "                    continue\n",
    "                m = max(m, f(a[i1] + 1, a[j1]))\n",
    "            return m + 2\n",
    "\n",
    "        return f(0, len(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        t = ''\n",
    "        for i in s:\n",
    "            t = i + t\n",
    "        n = len(s)\n",
    "        dp = [[0] * (n + 1) for i in range(n + 1)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)\n",
    "        return dp[n][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[None]*(n+2) for i in range(n+1)]\n",
    "        for i in range(n+1):\n",
    "            dp[0][i] = 0\n",
    "            dp[i][n+1] = 0\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(n, i, -1):\n",
    "                if s[i-1] == s[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j+1]+1\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i-1][j], dp[i][j+1])\n",
    "        max_val = -2**63\n",
    "        for i in range(0, n):\n",
    "            max_val = max(max_val, 2*dp[i][i+1], 2*dp[i][i+2]+1)\n",
    "        return max_val\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        self.memo = [[-1]*n for _ in range(n)]\n",
    "        return self.dp(s,0,n-1)\n",
    "    def dp(self,s,i,j):\n",
    "        if i>j:\n",
    "            return 0\n",
    "        if i == j:\n",
    "            return 1\n",
    "        if self.memo[i][j] != -1:\n",
    "            return self.memo[i][j]\n",
    "        if s[i] == s[j]:\n",
    "            self.memo[i][j] = self.dp(s,i+1,j-1)+2\n",
    "        else:\n",
    "            self.memo[i][j] = max(self.dp(s,i+1,j), self.dp(s,i,j-1))\n",
    "        return self.memo[i][j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        dp = [[0] * l for _ in range(l)]\n",
    "        for i in range(l):\n",
    "            dp[i][i] = 1\n",
    "        \n",
    "        for i in range(l - 1, -1, -1):\n",
    "            for j in range(i + 1, l):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "        \n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = np.zeros((n,n))\n",
    "        ans = 0\n",
    "        for i in range(0,n)[::-1]:\n",
    "            for j in range(i,n):\n",
    "                if i == j:\n",
    "                    dp[i,j] = 1\n",
    "                else:\n",
    "                    if s[i] == s[j]:\n",
    "                        dp[i,j] = dp[i+1,j-1]+2\n",
    "                    else:\n",
    "                        dp[i,j] = max(dp[i,j-1],dp[i+1,j])\n",
    "                ans = int(max(dp[i,j],ans))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class LCS:\n",
    "    def longestCommonSubsequence(self, text1: str, text2: str) -> int:\n",
    "        m, n = len(text1), len(text2)\n",
    "        dp = np.zeros([m+1, n+1], dtype=int)\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                if text1[i-1] == text2[j-1]:\n",
    "                    dp[i, j] = dp[i-1, j-1] + 1\n",
    "                else:\n",
    "                    dp[i, j] = max(dp[i-1, j], dp[i, j-1])\n",
    "        return dp[m,n]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        obj = LCS()\n",
    "        return int(obj.longestCommonSubsequence(s, s[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[1] * n for _ in range(n)]\n",
    "        # dp[i][j]表示s[i:j+1]中的最长回文子序列\n",
    "        # i == j:dp[i][j] = 1\n",
    "        # dp[i] == dp[j] and abs(i - j) == 1:dp[i][j] = 2\n",
    "        # dp[i] = dp[i+1][j-1] + 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if i == j:\n",
    "                        dp[i][j] = 1\n",
    "                    elif abs(i - j) == 1:\n",
    "                        dp[i][j] = 2\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "        return dp[0][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s_ = s[::-1]\n",
    "        dp = [[0]*(n+1) for _ in range(n+1)]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0]=i\n",
    "            dp[0][i]=i\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(1,n+1):\n",
    "                if s[i-1] == s_[j-1]:\n",
    "                    dp[i][j] = dp[i-1][j-1]\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1]+2,dp[i-1][j]+1,dp[i][j-1]+1)\n",
    "        \n",
    "        # print(dp)\n",
    "        return n-dp[-1][-1]//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        dp = [[0 for j in range(len(s)+1)] for i in range(len(s)+1)]\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])\n",
    "        return dp[0][len(s)-1] // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        r = ''.join(reversed(s))\n",
    "        s, r = s+'1', r+'2'\n",
    "        d = len(s)\n",
    "        common = [[int(s[i]==r[j]) for j in range(d)] for i in range(d)]\n",
    "        dp = [[0 for _ in range(d)] for _ in range(d)]\n",
    "\n",
    "        j = 0\n",
    "        while j < d:\n",
    "            dp[0][j] = common[0][j]\n",
    "            j += 1\n",
    "\n",
    "        longest = 0\n",
    "\n",
    "        i = 0\n",
    "        while i < d-1:\n",
    "            j = 0\n",
    "            while j < d-1:\n",
    "                longest = max(longest, dp[i][j])\n",
    "                if common[i][j]:\n",
    "                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+common[i+1][j+1])\n",
    "                else:\n",
    "                    dp[i][j+1] = max(dp[i][j+1], dp[i][j]+common[i][j+1])\n",
    "                    dp[i+1][j] = max(dp[i+1][j], dp[i][j]+common[i+1][j])\n",
    "                j += 1\n",
    "            i += 1\n",
    "\n",
    "        # for bar in dp:\n",
    "        #     print(bar)\n",
    "\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        dp=[[0]*2000 for _ in range(2000)]\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i]=1\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(i+1,len(s)):\n",
    "                if s[i]==s[j]:\n",
    "                    dp[i][j]=dp[i+1][j-1]+2\n",
    "                else:\n",
    "                    dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "        return dp[0][len(s)-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        dp = np.zeros((len(s),len(s)), dtype=int).tolist()\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = 1\n",
    "        for i in range(len(s)-1, -1,-1):\n",
    "            for j in range(i,len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j-i<=2:\n",
    "                        dp[i][j] =j-i+1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1],dp[i+1][j])\n",
    "        return dp[0][len(s)-1]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        length = len(s)\n",
    "        # 备忘录\n",
    "        # 字符串s在[i, j]范围内最长的回文子序列的长度为memo[i][j]\n",
    "        memo = [[-1] * length for _ in range(length)]\n",
    "        def dp(i, j):\n",
    "            if (i<0) or (j<0) or (i>=length) or (j>=length):\n",
    "                # 越界情况\n",
    "                return 0\n",
    "            if memo[i][j] != -1:\n",
    "                # 备忘录中有结果的话 使用备忘录\n",
    "                return memo[i][j]\n",
    "            # 开始条件判断\n",
    "            if s[i] == s[j]:\n",
    "                # 可以这么理解\n",
    "                # 假设有索引 i i+1 i+2 ..... j-1 j\n",
    "                # 如果s[i] == s[j], 那么 memo[i][j] = memo[i+1][j-1] + 2\n",
    "                memo[i][j] = dp(i+1, j-1) + 1\n",
    "            else:\n",
    "                memo[i][j] = max(\n",
    "                    # 还可以这么理解\n",
    "                    # 假设有索引 i i+1 i+2 ..... j-1 j\n",
    "                    # 如果 s[i] != s[j], 那么 memo[i][j] = max(memo[i][j-1], memo[i+1][j])\n",
    "                    # 加入s[i]\n",
    "                    dp(i, j-1),\n",
    "                    # 加入s[j]\n",
    "                    dp(i+1, j)\n",
    "                )\n",
    "            return memo[i][j]\n",
    "        return dp(0, length-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef __init__(self):\n",
    "\t\tself.f = {}\n",
    "\tdef longestPalindromeSubseq(self, s: str) -> int:\n",
    "\t\treturn self.dfs(0, len(s)-1, s)\n",
    "\n",
    "\tdef dfs(self, start, end, s):\n",
    "\t\tif (start, end) in self.f:\n",
    "\t\t\treturn self.f[(start, end)]\n",
    "\t\t\t\n",
    "\t\tif start > end:\n",
    "\t\t\treturn 0\n",
    "\t\tif start == end:\n",
    "\t\t\treturn 1\n",
    "\t\t\n",
    "\t\tif s[start] == s[end]:\n",
    "\t\t\treturn self.dfs(start+1, end-1, s) + 2\n",
    "\t\tval = max(self.dfs(start+1, end, s), self.dfs(start, end-1, s))\n",
    "\t\tself.f[(start, end)] = val\n",
    "\t\treturn val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq( self,s: str) -> int:\n",
    "        s_r = s[::-1]\n",
    "        dp = [[-1 for i in range(len(s))] for j in range(len(s))]\n",
    "        max_l = [1]\n",
    "        def common_str(s1,s2,i,j):\n",
    "            if i<0 or j<0:\n",
    "                return 0\n",
    "            if dp[i][j]!=-1:\n",
    "                return dp[i][j]\n",
    "            if s1[i]==s2[j]:\n",
    "                dp[i][j] = common_str(s1, s2, i-1, j-1)+1\n",
    "            else:\n",
    "                dp[i][j] = max(common_str(s1, s2, i-1, j),common_str(s1, s2, i, j-1))\n",
    "            max_l[0] = max(dp[i][j],max_l[0])\n",
    "            return dp[i][j]\n",
    "        common_str(s, s_r, len(s)-1, len(s)-1)\n",
    "        return max_l[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        path = [[-1] * n for row in range(n)]\n",
    "        # @cache\n",
    "        def dfs(i, j):#i为起始位置，j为终止位置\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if path[i][j] != -1:\n",
    "                return path[i][j]\n",
    "            if s[i] == s[j]:\n",
    "                path[i][j] = dfs(i + 1, j - 1) + 2;\n",
    "                return path[i][j]\n",
    "            path[i][j] = max(dfs(i,j-1),dfs(i+1,j))\n",
    "            return path[i][j]\n",
    "        return dfs(0,n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2 and s[0] == s[1]:\n",
    "            return 2\n",
    "        \n",
    "        dp = [ [-1]*(n) for _ in range(n)]\n",
    "        \n",
    "        def f(i, j):\n",
    "            nonlocal dp\n",
    "            nonlocal s\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            if i == j:\n",
    "                dp[i][j] = 1\n",
    "                return dp[i][j]\n",
    "            if i+1==j:\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = 2\n",
    "                else:\n",
    "                    dp[i][j] = 1\n",
    "                return dp[i][j]\n",
    "            dp[i][j] = max(f(i+1, j), f(i, j-1))\n",
    "            if s[i] == s[j]:\n",
    "                dp[i][j] = max(f(i, j), f(i+1, j-1)+2)\n",
    "            return dp[i][j]\n",
    "        \n",
    "        return f(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> str:\n",
    "        self.d = {}\n",
    "        res = self.dp(s, 0, len(s)-1)\n",
    "        return res\n",
    "    \n",
    "\n",
    "    def dp(self, s, i ,j):\n",
    "        if i == j:\n",
    "            return 1\n",
    "        if i > j:\n",
    "            return 0\n",
    "        if str(i) + \"_\" + str(j) in self.d:\n",
    "            return self.d[str(i) + \"_\" + str(j)]\n",
    "        if s[i] == s[j]:\n",
    "            res = self.dp(s, i+1,j-1) + 2\n",
    "            self.d[str(i) + \"_\" + str(j)] = res\n",
    "            return res\n",
    "        else:\n",
    "            res = max(self.dp(s, i+1 ,j), self.dp(s, i ,j-1))\n",
    "            self.d[str(i) + \"_\" + str(j)] = res\n",
    "            return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp_table = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp_table[i][i] = 1\n",
    "\n",
    "        def dp(s, start, end):\n",
    "            if dp_table[start][end] > 0:\n",
    "                return dp_table[start][end]\n",
    "            res = 0\n",
    "            if start == end:\n",
    "                res = 1\n",
    "            elif start > end:\n",
    "                res = 0\n",
    "            else:\n",
    "                res = max(dp(s, start, end-1), dp(s, start+1, end))\n",
    "                if s[start] == s[end]:\n",
    "                    res = max(res, dp(s, start+1, end-1)+2)\n",
    "            dp_table[start][end] = res\n",
    "            return res\n",
    "        return dp(s, 0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        memo = [ [-1]*n for _ in range(n) ]\n",
    "        def dp(start,end):\n",
    "            if start > end:\n",
    "                return 0\n",
    "            if start == end:\n",
    "                return 1\n",
    "            if memo[start][end] != -1:\n",
    "                return memo[start][end]\n",
    "            if s[start] == s[end]:\n",
    "                memo[start][end] = dp(start+1,end-1) + 2\n",
    "            else:\n",
    "                memo[start][end] = max(dp(start,end-1),dp(start+1,end))\n",
    "            return memo[start][end]\n",
    "        return dp(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        self.memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]\n",
    "        def dp(i, j):\n",
    "            if i == j: return 1\n",
    "            if i > j: return 0\n",
    "            # print(i , j)\n",
    "            if self.memo[i][j] != -1: return self.memo[i][j]\n",
    "            if s[i] == s[j]: self.memo[i][j] = dp(i+1, j-1) + 2\n",
    "            else:\n",
    "                self.memo[i][j] = max(dp(i+1, j), dp(i, j-1))\n",
    "            return self.memo[i][j]\n",
    "        return dp(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lgs(self,s,i,j,memo):\n",
    "        if i == j: return 1\n",
    "        if i > j: return 0\n",
    "        if (i,j) in memo:\n",
    "            return memo[(i,j)]\n",
    "        if s[i] == s[j]:\n",
    "            memo[(i,j)] = self.lgs(s,i+1,j-1,memo) + 2\n",
    "        else:\n",
    "            memo[(i,j)] = max(self.lgs(s,i,j-1,memo),self.lgs(s,i+1,j,memo))\n",
    "        return memo[(i,j)]\n",
    "\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        memo = {}\n",
    "        return self.lgs(s,0,len(s)-1,memo)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        @cache    \n",
    "        def dfs(i:int,j:int)->int:\n",
    "            if i>j:return 0\n",
    "            if i==j:return 1\n",
    "            if s[i]==s[j]:\n",
    "                return dfs(i+1,j-1)+2\n",
    "            else:\n",
    "                return max(dfs(i+1,j),dfs(i,j-1))\n",
    "        ans=dfs(0,len(s)-1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        def solve(s,i,j):\n",
    "            if db[i][j]!=-1:\n",
    "                return db[i][j]\n",
    "            if i==j:\n",
    "                db[i][j]=1\n",
    "                return 1\n",
    "            elif i>j:\n",
    "                db[i][j] = 0\n",
    "                return 0\n",
    "            else:\n",
    "                if s[i] == s[j]:\n",
    "                    db[i][j] =solve(s,i+1,j-1)+2\n",
    "                else:\n",
    "                    db[i][j] =max(solve(s,i+1,j),solve(s,i,j-1))\n",
    "                return db[i][j]\n",
    "        n = len(s)\n",
    "        db =  [[-1] * n for i in range(n)]\n",
    "        return solve(s,0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sub_fun(self, start, end):\n",
    "        if (start, end) in self.dic:\n",
    "            return self.dic[(start,end)]\n",
    "\n",
    "        ret = 0\n",
    "        if start == end:\n",
    "            ret = 1\n",
    "        elif end-start == 1:\n",
    "            if self.s[start] == self.s[end]:\n",
    "                ret = 2\n",
    "            else:\n",
    "                ret = 1\n",
    "        else:\n",
    "            if self.s[start] == self.s[end]:\n",
    "                ret = max(self.sub_fun(start, end-1), self.sub_fun(start+1, end), 2+self.sub_fun(start+1, end-1))\n",
    "            else:\n",
    "                ret = max(self.sub_fun(start, end-1), self.sub_fun(start+1, end))\n",
    "\n",
    "        self.dic[(start,end)] = ret\n",
    "        return ret\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        self.dic =dict()\n",
    "        self.s = s\n",
    "        return self.sub_fun(0, len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        dp = collections.defaultdict(int)\n",
    "        for length in range(1, len(s)):\n",
    "            for i in range(len(s) - length):\n",
    "                add = 0\n",
    "                if s[i] == s[i + length]:\n",
    "                    add += 2\n",
    "                if length == 2:\n",
    "                    add += 1\n",
    "                elif length == 1:\n",
    "                    add = max(1, add)\n",
    "                dp[(i, length)] = max(dp[(i + 1, length - 2)] + add, dp[(i + 1, length - 1)], dp[(i, length - 1)])\n",
    "        \n",
    "        return dp[(0, len(s) - 1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from functools import cache\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        positions = defaultdict(list)\n",
    "        for i, c in enumerate(s):\n",
    "            positions[c].append(i)\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return 2 + f(i+1, j-1)\n",
    "\n",
    "            ii = bisect.bisect_left(positions[s[i]], i)\n",
    "            kk = bisect.bisect_left(positions[s[i]], j, ii) - 1\n",
    "            k = positions[s[i]][kk]\n",
    "            if k == i:\n",
    "                res1 = 1\n",
    "            else:\n",
    "                res1 = 2 + f(i + 1, k - 1)\n",
    "\n",
    "            res2 = f(i + 1, j)\n",
    "            return max(res1, res2)\n",
    "\n",
    "        result = f(0, len(s) - 1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.record=None\n",
    "    def f(self,m,n,s):\n",
    "        if m+1==n or m==n:return\n",
    "        if self.record[m+1,n-1] is None:\n",
    "            self.f(m+1,n-1,s)\n",
    "        if self.record[m+1,n] is None:\n",
    "            self.f(m+1,n,s)\n",
    "        if self.record[m,n-1] is None:\n",
    "            self.f(m,n-1,s)\n",
    "        if s[m]==s[n]:\n",
    "            self.record[m,n]=self.record[m+1,n-1]+2\n",
    "        else:\n",
    "            self.record[m,n]=max(self.record[m+1,n],self.record[m,n-1])\n",
    "\n",
    "\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        l=len(s)\n",
    "        self.record={}\n",
    "        for i in range(l):\n",
    "            for j in range(i,l):\n",
    "                if i==j:\n",
    "                    self.record[i,j]=1\n",
    "                elif i+1==j:\n",
    "                    if s[i]==s[j]:\n",
    "                        self.record[i,j]=2\n",
    "                    else:\n",
    "                        self.record[i,j]=1\n",
    "                else:\n",
    "                    self.record[i,j]=None\n",
    "        self.f(0,l-1,s)\n",
    "        return self.record[0,l-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @lru_cache(maxsize = n*n)\n",
    "        def f(i:int,j:int) -> int:\n",
    "            if i > j :\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return f(i +1,j-1) +2\n",
    "            return max(f(i,j-1),f(i+1,j))\n",
    "\n",
    "        ans = f(0,n-1)\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        @cache\n",
    "        def f(i: int, j: int):\n",
    "            if i < 0 or j >= n:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                res = f(i - 1, j + 1)\n",
    "                if res <= 0:\n",
    "                    return len(s[i: j + 1])\n",
    "                return res\n",
    "            else:\n",
    "                return max(f(i - 1, j), f(i, j + 1)) - 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, f(i, i), f(i, i + 1))\n",
    "        f.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        d = defaultdict(list)\n",
    "        for i, j in enumerate(s):\n",
    "            d[j].append(i)\n",
    "\n",
    "        @cache\n",
    "        def f(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return f(i + 1, j - 1) + 2            \n",
    "            right = bisect_left(d[s[i]], j) - 1\n",
    "            res = f(i, d[s[i]][right])\n",
    "            left = bisect_left(d[s[j]], i)\n",
    "            res = max(res, f(d[s[j]][left], j), f(i + 1, j - 1))\n",
    "            return res \n",
    "        \n",
    "        return f(0, n - 1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        H = [[-1]*len(s) for _ in range(len(s))]\n",
    "        def find(i,j):\n",
    "            if H[i][j]!=-1:return H[i][j]\n",
    "            if i>j:return 0\n",
    "            if i == j:\n",
    "                H[i][j] = 1\n",
    "                return H[i][j]\n",
    "            if s[i]==s[j]:\n",
    "                H[i][j] = find(i+1,j-1)+2\n",
    "                return H[i][j]\n",
    "            H[i][j] = max(H[i][j],find(i+1,j))\n",
    "            H[i][j] = max(H[i][j],find(i,j-1))\n",
    "            H[i][j] = max(H[i][j],find(i+1,j-1))\n",
    "            return H[i][j]\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,len(s)):\n",
    "                res = max(res,find(i,j))\n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        lens = len(s)\n",
    "        dp = [[-1 for _ in range(lens)] for _ in range(lens)]\n",
    "        def dfs(i,j):\n",
    "            if type(dp[i][j])==str: return dp[i][j]\n",
    "            if j==i:\n",
    "                dp[i][j] = s[i:j+1]\n",
    "            elif i>j:\n",
    "                dp[i][j] = ''\n",
    "            elif s[i]==s[j]:\n",
    "                dp[i+1][j-1] = dfs(i+1, j-1)\n",
    "                dp[i][j] = s[i] + dp[i+1][j-1] + s[j]\n",
    "            else:\n",
    "                dp[i+1][j] = dfs(i+1, j)\n",
    "                dp[i][j-1] = dfs(i, j-1)\n",
    "                if len(dp[i+1][j])>len(dp[i][j-1]):\n",
    "                    dp[i][j] = dp[i+1][j]\n",
    "                else:\n",
    "                    dp[i][j] = dp[i][j-1]\n",
    "            return dp[i][j]\n",
    "        return len(dfs(0, lens-1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        # 尝试模型\n",
    "        # 返回以s[l:r]范围内的最长回文子序列长度\n",
    "        def p(l, r):\n",
    "            # base case\n",
    "            if l == r:\n",
    "                return 1\n",
    "            if l > r:\n",
    "                return 0\n",
    "            name = '{},{}'.format(l, r)\n",
    "            if name in dp:\n",
    "                return dp[name]\n",
    "            # 状态转移\n",
    "            # 情况一，两个边界都被匹配了\n",
    "            if s[l] == s[r]:\n",
    "                res = p(l+1, r-1) + 2\n",
    "            # 情况二，两个边界只有一个被匹配，或者都没匹配\n",
    "            else:\n",
    "                res = max(p(l+1, r), p(l, r-1), p(l+1, r-1))\n",
    "            dp[name] = res\n",
    "            return res\n",
    "        dp = {}\n",
    "        length = p(0, len(s)-1)\n",
    "        return length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s):\n",
    "        \"\"\"\n",
    "        思路：\n",
    "        遇到一个数组，如果求其最大、最小、最长、最短的个数，而不需要知道具体解的问题，一般考虑         动态规划。\n",
    "\n",
    "        我们在考虑动态规划的转移方程的时候，一定切记，转移方程右边部分（子问题）认为是满足题设         条件的。\n",
    "        \n",
    "        用dp[i][j]表示i,j之间的最长子序列长度，那么可得以下动态方程\n",
    "        dp[i][j]=0, if i>j\n",
    "        dp[i][j]=1, if i=j\n",
    "        dp[i][j]=dp[i+1][j-1] + 2, if s[i]=s[j]\n",
    "        dp[i][j]=max(dp[i+1][j],dp[i][j-1]), if s[i] != s[j]\n",
    "        \n",
    "        由于计算d[i][j]时需要引用i+1，所以i+1一定已经计算出来了，所以i从s的尾部开始遍历\n",
    "        \n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not s:\n",
    "            return 0\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        i = n-1\n",
    "        while i >= 0:\n",
    "            dp[i][i] = 1\n",
    "            j = i+1\n",
    "            while j < n:\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i+1][j-1] + 2\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j],dp[i][j-1])\n",
    "                j += 1\n",
    "            i -= 1\n",
    "         \n",
    "        return dp[0][n-1]\n",
    "        \n",
    "        \n",
    "        \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        dp = [ [0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for l in range(1,n):\n",
    "            for i in range(n-1):\n",
    "                j = i+l\n",
    "                if j < n:\n",
    "                    if s[i]==s[j]:\n",
    "                        dp[i][j]=2+dp[i+1][j-1]\n",
    "                    else:\n",
    "                        dp[i][j]=max(dp[i+1][j],dp[i][j-1])\n",
    "        return dp[0][n-1]\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from functools import lru_cache\n",
    "import sys\n",
    "sys.setrecursionlimit(1000000000)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s):\n",
    "        self.cache = {}\n",
    "        # result = 0\n",
    "        # max_char = \"\"\n",
    "        # # for i in range(len(s)):\n",
    "        next_result, sub_str = self.digui(0, len(s)-1, s)\n",
    "        # if result < next_result:\n",
    "        #     result = next_result\n",
    "        #     max_char = sub_str\n",
    "        return next_result\n",
    "\n",
    "    # @lru_cache(maxsize=18000000)\n",
    "    def digui(self, i, j, s):\n",
    "        if (i, j) in self.cache:\n",
    "            return self.cache[(i, j)]\n",
    "\n",
    "        if i > j:\n",
    "            self.cache[(i, j)] = (0, \"\")\n",
    "            return 0, \"\"\n",
    "\n",
    "        if i == j:\n",
    "            self.cache[(i, j)] = (1, s[i])\n",
    "            return 1, s[i]\n",
    "\n",
    "        if s[i] == s[j]:\n",
    "            # print(\"++2\")\n",
    "            lengh, sub_char = self.digui(i+1, j-1, s)\n",
    "            self.cache[(i, j)] = lengh + 2, s[i] + sub_char + s[j]\n",
    "            return lengh + 2, s[i] + sub_char + s[j]\n",
    "        # elif right_index - left_index == 0:\n",
    "        #     return 1, s[left_index]\n",
    "        else:\n",
    "            lengh_a, sub_char_a = self.digui(i+1, j, s)\n",
    "            lengh_b, sub_char_b = self.digui(i, j-1, s)\n",
    "            if lengh_a > lengh_b:\n",
    "                self.cache[(i, j)] = (lengh_a, sub_char_a)\n",
    "                return lengh_a, sub_char_a\n",
    "\n",
    "            self.cache[(i, j)] = lengh_b, sub_char_b\n",
    "            return lengh_b, sub_char_b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        memo = {}\n",
    "        return self.dp(s, 0, len(s) - 1, memo)\n",
    "\n",
    "\n",
    "    def dp(self, s, i, j, memo):\n",
    "        if i >= len(s) or j >= len(s) or i < 0 or j < 0:\n",
    "            return 0\n",
    "\n",
    "        key = str(i) + '#' + str(j)\n",
    "        if key in memo:\n",
    "            return memo[key]\n",
    "\n",
    "        if s[i] == s[j]:\n",
    "            memo[key] = self.dp(s, i + 1, j - 1, memo) + 1\n",
    "        else:\n",
    "            memo[key] = max(self.dp(s, i, j - 1, memo), self.dp(s, i + 1, j, memo))\n",
    "\n",
    "        return memo[key]\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        memo = {}\n",
    "        def rec(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if s[i] == s[j]:\n",
    "                return rec(i + 1, j - 1) + 2\n",
    "            memo[(i, j)] = max(rec(i + 1, j), rec(i, j - 1), rec(i + 1, j - 1))\n",
    "            return memo[(i, j)]\n",
    "        return rec(0, len(s) -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @lru_cache(100000)\n",
    "        def f(i:int, j:int):\n",
    "            if i>j: return 0\n",
    "            if i==j: return 1\n",
    "            if s[i]==s[j]: return f(i+1, j-1) + 2\n",
    "            else: return max(f(i+1, j), f(i, j-1))\n",
    "        return f(0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSeq(self, s: str, start: int, end: int):\n",
    "        if (start > end):\n",
    "            return 0\n",
    "        if (start == end):\n",
    "            return 1\n",
    "        str = s[start:end+1]\n",
    "        if str in self.childResult:\n",
    "            return self.childResult[str]\n",
    "        arr = self.charMap[s[start]]\n",
    "        if arr == None:\n",
    "            arr = []\n",
    "        newEnd = 100000\n",
    "        popArr = []\n",
    "        while (len(arr) > 0 and newEnd > end and newEnd > start):\n",
    "            newEnd = arr.pop()\n",
    "            popArr.append(newEnd)\n",
    "        result = 1 if len(arr) == 0 or newEnd <= start else self.longestSeq(\n",
    "            s, start + 1, newEnd - 1) + 2\n",
    "        popArr.reverse()\n",
    "        arr.extend(popArr)\n",
    "        self.charMap[s[start]] = arr\n",
    "        result = max(result,\n",
    "                     self.longestSeq(s, start + 1, end))\n",
    "        # if (s[start] == s[end]):\n",
    "        #     result = self.longestSeq(s, start + 1, end - 1) + 2\n",
    "        # else:\n",
    "        #     result = max(self.longestSeq(s, start + 1, end),\n",
    "        #                  self.longestSeq(s, start, end - 1))\n",
    "        self.childResult[str] = result\n",
    "        return result\n",
    "\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        charMap = {}\n",
    "        self.childResult = {}\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            if c in charMap:\n",
    "                charMap[c].append(i)\n",
    "            else:\n",
    "                charMap[c] = [i]\n",
    "        self.charMap = charMap\n",
    "        return self.longestSeq(s, 0, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        self.cache = {}\n",
    "        return self.find(s)\n",
    "    \n",
    "    def find(self, s):\n",
    "        if s in self.cache:\n",
    "            return self.cache[s]\n",
    "        if not s:\n",
    "            return 0\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "        if s[0] == s[-1]:\n",
    "            self.cache[s] = self.find(s[1:-1]) + 2\n",
    "            return self.cache[s]\n",
    "        else:\n",
    "            self.cache[s] = max(self.find(s.lstrip(s[0])), self.find(s.rstrip(s[-1])))\n",
    "            return self.cache[s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s):\n",
    "        length = len(s)\n",
    "        dp = [[1 for i in range(length)] for j in range(length)]\n",
    "        for i in range(length):\n",
    "            for j in range(length-i):\n",
    "                if s[j] == s[j+i]:\n",
    "                    if j+1 == j+i:\n",
    "                        dp[j][j+i] = 2\n",
    "                    elif j+1 <= j+i-1:\n",
    "                        dp[j][j+i] = dp[j+1][j+i-1] + 2\n",
    "                else:\n",
    "                        dp[j][j+i] = max(dp[j][i+j-1], dp[j+1][i+j])\n",
    "        return dp[0][length-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def fn(i,j):\n",
    "            if i>j:\n",
    "                return 0\n",
    "            if i==j:\n",
    "                return 1\n",
    "            if s[i]==s[j]:\n",
    "                return fn(i+1,j-1)+2\n",
    "            return max(fn(i+1,j),fn(i,j-1))\n",
    "        \n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        def fn2(i,j):\n",
    "            if dp[i][j]:\n",
    "                return dp[i][j]\n",
    "            c = 0\n",
    "            if i>j:\n",
    "                return 0\n",
    "            elif i==j:\n",
    "                c = 1\n",
    "            elif s[i]==s[j]:\n",
    "                c = fn(i+1,j-1)+2\n",
    "            else:\n",
    "                c = max(fn(i+1,j),fn(i,j-1))\n",
    "            dp[i][j]=c\n",
    "            return c\n",
    "        return fn2(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(maxsize=None)\n",
    "    def pal_length(self, l, r):\n",
    "        if l == r:\n",
    "            return 1\n",
    "        if l > r:\n",
    "            return 0\n",
    "        if self.data[l] == self.data[r]:\n",
    "            return self.pal_length(l + 1, r - 1) + 2\n",
    "        else:\n",
    "            return max(self.pal_length(l + 1, r), self.pal_length(l, r - 1))\n",
    "\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        self.data = s\n",
    "        return self.pal_length(0, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        t = s[::-1]\n",
    "        n = len(s)\n",
    "        # 解法一: 转化成LCS, 由于回文序列 -> 正读 = 反读, 逆转s求 [LCS]\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if s[i - 1] == t[j - 1]:\n",
    "                    f[i][j] = f[i-1][j-1] + 1\n",
    "                else:\n",
    "                    f[i][j] = max(f[i-1][j], f[i][j-1])\n",
    "        \n",
    "        # return f[-1][-1]\n",
    "        # 解法二: 区间DP\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            \n",
    "            # 如果选\n",
    "            res = 1\n",
    "            if s[i] == s[j]:\n",
    "                res = max(res, dfs(i + 1, j - 1) + 2)\n",
    "            else:\n",
    "                res = max(res, dfs(i + 1, j), dfs(i, j - 1))\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, n - 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        s1, s2 = s, list(reversed(s))\n",
    "\n",
    "        from collections import defaultdict\n",
    "\n",
    "        f = defaultdict(int)\n",
    "\n",
    "        for i, c1 in enumerate(s1):\n",
    "            for j, c2 in enumerate(s2):\n",
    "                f[i, j] = max(f[i-1, j], f[i, j-1], f[i-1, j-1] + 1 if c1 == c2 else 0)\n",
    "\n",
    "        n = len(s)\n",
    "        return f[n-1, n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:     \n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        if n <= 1: return n\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l >= r: return 1 if l == r else 0\n",
    "           # if not dp[l][r]:\n",
    "           #     return dp[l][r]\n",
    "            while l < r:\n",
    "        \n",
    "                if s[l] == s[r]:\n",
    "                    res = dfs(l+1,r-1)+2\n",
    "       \n",
    "                else:\n",
    "                    \n",
    "                    res = max(dfs(l+1,r), dfs(l,r-1))\n",
    "              #  dp[l][r]=res\n",
    "                return res\n",
    "                \n",
    "            \n",
    "\n",
    "        return dfs(0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\r\n",
    "        df = {(i,j):0 for i in range(len(s)) for j in range(len(s))}\r\n",
    "        for d in range(len(s)):\r\n",
    "            for i in range(len(s) - d):\r\n",
    "                j = i + d\r\n",
    "                if d == 0:\r\n",
    "                    df[(i,j)] = 1\r\n",
    "                elif s[i] == s[j]:\r\n",
    "                    df[(i,j)] = df[(i+1,j-1)] + 2\r\n",
    "                else:\r\n",
    "                    df[(i,j)] = max(df[(i+1,j)], df[(i,j-1)])\r\n",
    "        # print(df)\r\n",
    "        return df[(0,len(s)-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        self.l = len(s)\n",
    "        self.s = s\n",
    "        self.sr = s[::-1]\n",
    "        self.memo = {(i,j):-1 for i in range(self.l+1) for j in range(self.l+1)}\n",
    "        self.dp(0,0)\n",
    "        # print(self.memo)\n",
    "        return self.memo[(0,0)]\n",
    "\n",
    "    def dp(self,i,j):\n",
    "        if i == self.l or j == self.l:\n",
    "            self.memo[(i,j)] = 0\n",
    "            return 0\n",
    "        if self.memo[(i,j)]!=-1:\n",
    "            return self.memo[(i,j)]\n",
    "        if self.s[i] == self.sr[j]:\n",
    "            self.memo[(i,j)] = self.dp(i+1,j+1) + 1\n",
    "        else:\n",
    "            self.memo[(i,j)] = max(self.dp(i+1,j),self.dp(i,j+1))\n",
    "        return self.memo[(i,j)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        print_matrix = [[0] * s.__len__() for _ in range(s.__len__())]\n",
    "\n",
    "        # dp(i,j) is from s[i] to s[j], the max length of palindrome\n",
    "        @cache\n",
    "        def dp(i: int, j: int) -> int:\n",
    "            if not 0 <= i <= j < s.__len__():\n",
    "                print_matrix[i][j] = 0\n",
    "                return 0\n",
    "            if i == j:\n",
    "                print_matrix[i][j] = 1\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                print_matrix[i][j] = 2 + dp(i + 1, j - 1)\n",
    "                return 2 + dp(i + 1, j - 1)\n",
    "            else:\n",
    "                print_matrix[i][j] = max(dp(i + 1, j), dp(i, j - 1))\n",
    "                return max(dp(i + 1, j), dp(i, j - 1))\n",
    "\n",
    "        return dp(0, s.__len__() - 1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        \n",
    "        output = {}\n",
    "        output[''] = 0\n",
    "        for i in range(1,len(s)+1):\n",
    "            for j in range(len(s)-i+1):\n",
    "                output[s[j:j+i]] = 1\n",
    "\n",
    "        for key in output.keys():\n",
    "            if len(key)==1 or len(key)==0:\n",
    "                continue\n",
    "            output[key] = 2+output[key[1:-1]] if key[0]==key[-1] else max(output[key[1:]],output[key[:-1]])\n",
    "        return output[s]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        import functools\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            if s[i:j+1] == s[i:j+1][::-1]:return j-i+1\n",
    "            if i > j: return 0\n",
    "            res = 0\n",
    "            if s[i] == s[j]:\n",
    "                res = max(res, 2 + dfs(i + 1, j - 1))\n",
    "            return max(res, dfs(i + 1, j), dfs(i, j - 1))\n",
    "        \n",
    "        return dfs(0, len(s) - 1)\n",
    "'''\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0] * n for _ in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            dp[i][i] = 1\n",
    "            for j in range(i + 1, n, 1):\n",
    "                if s[j] == s[i]:\n",
    "                    dp[i][j] = 2 + dp[i + 1][j - 1]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])\n",
    "        return dp[0][n - 1]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    " \n",
    "        dp = [[-1] * n for _ in range(n)]\n",
    "        @cache\n",
    "        def dfs(left:int, right:int) -> int:\n",
    "            if dp[left][right] != -1:\n",
    "                return dp[left][right]\n",
    "\n",
    "            if left > right:\n",
    "                return 0\n",
    "            if left == right:\n",
    "                dp[left][right] = 1\n",
    "                return 1\n",
    "\n",
    "            if s[left] == s[right]:\n",
    "\n",
    "                dp[left][right] = dp[left+1][right-1] + 2 \n",
    "\n",
    "                return dfs(left + 1,right - 1) + 2\n",
    "\n",
    "            else:\n",
    "                dp[left][right] = max(dp[left][right-1],dp[left+1][right])\n",
    "                return  max(dfs(left, right - 1),dfs(left + 1, right))   \n",
    "\n",
    "        return dfs(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[''] * n for i in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = s[i]\n",
    "        max_len = 1\n",
    "\n",
    "        for L in range(2, n+1):\n",
    "            for i in range(n):\n",
    "                j = L + i - 1\n",
    "                if j >= n:\n",
    "                    break\n",
    "                if s[i] == s[j]:\n",
    "                    if L < 3:\n",
    "                        dp[i][j] = s[i] + s[j]\n",
    "                    else:\n",
    "                        dp[i][j] = s[i] + dp[i+1][j-1] + s[j]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1], key=lambda x: len(x))\n",
    "                if len(dp[i][j]) > max_len:\n",
    "                    max_len = len(dp[i][j])\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(i,j):\n",
    "            if i==j:\n",
    "                return 1\n",
    "            elif i>j:\n",
    "                return 0\n",
    "            elif s[i]==s[j]:\n",
    "                return dp(i+1,j-1) + 2\n",
    "            else:\n",
    "                return max(dp(i+1,j), dp(i,j-1))\n",
    "        return dp(0,len(s)-1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        \n",
    "        #思路：动态规划 DPtable优化\n",
    "        # dp = [[0] * len(s) for _ in range(len(s))]\n",
    "        # for i in range(len(s)):\n",
    "        #     dp[i][i] = 1 \n",
    "        # for i in range(len(s) - 2,-1,-1):\n",
    "        #     for j in range(i + 1,len(s)):\n",
    "        #         if s[i] == s[j]:\n",
    "        #             dp[i][j] = dp[i + 1][j - 1] + 2\n",
    "        #         else:\n",
    "        #             dp[i][j] = max(dp[i + 1][j],dp[i][j - 1])\n",
    "        # return dp[0][len(s) - 1]\n",
    "\n",
    "        memo = dict()\n",
    "        def dp(i,j):\n",
    "            if (i,j) in memo:\n",
    "                return memo[(i,j)]\n",
    "            if i > j:\n",
    "                return 0 \n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                memo[(i,j)] = dp(i + 1,j - 1) + 2\n",
    "            else:\n",
    "                memo[(i,j)] = max(dp(i + 1,j),dp(i,j - 1))\n",
    "            return memo[(i,j)]\n",
    "        return dp(0,len(s) - 1)\n",
    "\n",
    "        # def dp(i,j):\n",
    "        #     if i > j:\n",
    "        #         return 0\n",
    "        #     if i == j:\n",
    "        #         return 1\n",
    "            \n",
    "        #     if s[i]==s[j]:\n",
    "        #         return dp(i+1,j-1)+2\n",
    "        #     else:\n",
    "        #         return max(dp(i+1,j),dp(i,j-1))\n",
    "        # return dp(0,len(s)-1)\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\r\n",
    "        # \r\n",
    "        moke = {}\r\n",
    "        def func(i, j):\r\n",
    "            if i==j: return 1\r\n",
    "            if i==j-1: return 2 if s[i]==s[j] else 1\r\n",
    "            if (i, j) in moke: return moke[(i, j)]\r\n",
    "            if s[i] == s[j]:\r\n",
    "                moke[(i, j)] = 2 + func(i+1, j-1)\r\n",
    "            else:\r\n",
    "                moke[(i, j)] = max(func(i, j-1), func(i+1, j))\r\n",
    "            return moke[(i, j)]\r\n",
    "\r\n",
    "        if not s:\r\n",
    "            return 0\r\n",
    "        return func(0, len(s)-1)\r\n",
    "\r\n",
    "\r\n",
    "        # if not s:\r\n",
    "        #     return 0\r\n",
    "        # n = len(s)\r\n",
    "        # dp = [[0] * n for i in range(0, n)]\r\n",
    "        # for i in range(n-1, -1, -1):\r\n",
    "        #     dp[i][i] = 1\r\n",
    "        #     for j in range(i+1, n):\r\n",
    "        #         if s[i] == s[j]:\r\n",
    "        #             dp[i][j] = dp[i+1][j-1] + 2\r\n",
    "        #         else:\r\n",
    "        #             dp[i][j] = max(dp[i+1][j], dp[i][j-1])\r\n",
    "        \r\n",
    "        # for i in dp:\r\n",
    "        #     print(i)\r\n",
    "        # return dp[0][n-1]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        @cache\n",
    "        def f(a,b):\n",
    "            if a > b: return 0\n",
    "            if a == b: return 1\n",
    "            if s[a] == s[b]: return f(a+1,b-1)+2\n",
    "            else: return max(f(a,b-1),f(a+1,b))\n",
    "        return f(0,len(s)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l > r: return 0\n",
    "            if l == r: return 1\n",
    "            res = dfs(l + 1, r - 1)\n",
    "            if s[l] == s[r]: return dfs(l + 1, r - 1) + 2\n",
    "            res = max(res, dfs(l, r - 1))\n",
    "            res = max(res, dfs(l + 1, r))\n",
    "            return res\n",
    "        return dfs(0, len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindromeSubseq(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if i == j:\n",
    "                return 1\n",
    "            if s[i] == s[j]:\n",
    "                return 2+dfs(i+1,j-1)\n",
    "            else:\n",
    "                return max(dfs(i+1,j),dfs(i,j-1))\n",
    "        return dfs(0,n-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
